// 164. 最大间距

/**
 * 基数排序
 */
function indexSort(num:number[]):number[]{
    
    let exp = 1
    const maxValue = Math.max(...num)
    const buf = new Array(num.length).fill(0)

    while(exp<=maxValue){
        const cnt = new Array(10).fill(0)
        for(let n of num){
            let digit = Math.floor(n/exp)%10
            cnt[digit]++
        }
        for(let i=1;i<10;i++){
            cnt[i] += cnt[i-1]
        }
        for(let i=num.length-1 ;i>=0;i--){
            const n = num[i]
            let digit = Math.floor(n/exp)%10
            buf[cnt[digit]-1] = n
            cnt[digit]--
        }
        num.splice(0,num.length,...buf)
        exp*=10
    }
    return num
}

function maximumGap(nums: number[]): number {
    if(nums.length<2) return 0
    indexSort(nums)
    let last = nums[0]
    let max = 0
    for(let i = 1 ;i<nums.length;i++){
        max = Math.max(max,nums[i]-last)
        last = nums[i]
    }
    return max
};
